In multiprocessor computer systems, multiple processes execute concurrently on the multiple processors. These processes often share resources, such as storage devices, input/output devices and memory. When two or more processes need to operate on the same data in memory, or on the same device, it becomes necessary to provide a mechanism to enforce mutually exclusive access to the resources. Such a mechanism is also required in a single processor system which supports pre-emptive multitasking of processes. In other words, a mechanism is required to allow only one process to have access to a resource at any one time.
A semaphore is a synchronization mechanism which mediates access to shared resources. When a process has acquired a semaphore, it is not possible for any other process to acquire the semaphore until the first process has released the semaphore. Thus, semaphores are used to guarantee mutual exclusion of shared resources.
In a system where multiple processes operate on shared data and acquire semaphores, it is possible for a process to acquire a semaphore and then fail (typically due to a software bug in the process that causes the operating system to terminate the process). Unless corrective action is taken, the semaphore will not be released since the process is no longer alive to release it. This can severely affect the functioning of other processes that want to access the shared resource. Until the semaphore is recovered, other processes will be excluded from acquiring the semaphore and accessing the resource.
In order to perform recovery actions on a semaphore which is held by a failed process and release it, a system can either (a) determine which process failed while holding the semaphore and perform recovery actions on a process level, or (b) perform recovery actions on a system level by terminating all processes that could have acquired the semaphore and reinitializing the entire system, including the semaphores. System level recovery could severely affect availability of a system, and is not desirable in many contexts. In a system in which the multiple processes are tightly coupled, i.e. all processes are working on a common task, the problem of not being able to determine whether a crashed process held a semaphore is not a significant problem. If a process crashes, the entire computation must be restarted anyway, and recovering all the resources and resetting the semaphores does not add significant cost to reinitializing the system. However, the indeterminate aspect of semaphore ownership becomes a problem in a system in Which many of the processes are unrelated. In such a system, if one process crashes, it is desirable to allow the other processes to continue running uninterrupted. It is therefore desirable to be able to detect which process failed while holding a semaphore and perform a process level recovery.
Detecting which process failed while holding a semaphore is straightforward if system semaphores are used. System semaphores are semaphores which are implemented within the operating system kernel. However, semaphores provided by typical operating systems are very slow. Semaphores implemented at the user level (also known as spin-locking semaphores) are widely used because of their speed, and are important in time critical applications. However, with such semaphores, it is possible for process failure at critical points in the semaphore acquisition code to leave the system in a state where it is not clear which process holds a semaphore, making it impossible to perform recovery actions on a per process basis.
The present invention provides for semaphores implemented at the user level while allowing the system to determine when a failed process holds a semaphore regardless of when the process may have failed. Thus, the invention allows fault-tolerant systems to be built using a natural and high-performance architecture for sharing resources using fast user level semaphores for synchronization.